Network performance relies in part on the rate at which network nodes can handle incoming packets. The node must be capable of handling packets at least as fast as the packets arrive.
The nodes analyze a packet to determine where to send the packet. The node can make a decision whether to and where the packet should be forwarded, for example, based upon a source network location or destination network location identified by the packet. The speed with which the node is able to act on the packet is a limiting factor for network performance.
There are established network protocols relating to address resolution. Node throughput is based at least in part on the speed with which the destination port can be determined from the packet-provided network location. Typically the node maintains a lookup table that aids in determining which port to forward a packet to. There may be a very large space of possible addresses that the node must be capable of handling, however, the table memory inherently has a finite storage space. The lookup table associates a network location with a data value such as the port to forward a packet having that network location.
One approach for achieving a fast lookup uses content addressable memories (CAM). A typical memory returns data located at a specified memory address. A CAM permits simultaneous comparison of an M-bit match section of every table entry with a given value to identify the location of table entry having a match section matching the packet-provided network location. The length of time required for the search is independent of the size of the lookup table. However, for a 2k entry table, a CAM requires die space sufficient to implement M 2k-input comparators and thus can require significant die space depending upon the size of the table and the width of the network location.
Another approach uses a hash function to compress the potential addressable network space to fit within the finite memory provided for the lookup table. A received network location is hashed to identify a specific entry in the lookup table. Due to the finite table lookup memory and the potentially very large addressable network space, the hash function is likely to generate the same address in memory for many different network locations. The result is a “collision”. Collisions require rehashing to identify alternate locations or other techniques in order to avoid reuse of the already used memory location. Given that the table is expected to be nearly full for efficient use of die space, there is a high probability of collision. The hash function can make efficient use of the finite storage space, however, the performance hit due to collisions may render a hash approach impractical for high-speed applications.